As the internet continues to gain popularity, the need to store sensitive personal information on untrusted server computers is growing. For example, in order to provide users with fast response times, many organizations are offloading data storage and processing to third-party data centers geographically close to users. In addition, storage as a service and other “cloud” services are gaining popularity with organizations for cost and scalability reasons. Typically, these services are operated by third party organizations with uncertain security standards. Thus, ensuring the security of data at rest continues to be a necessity.
In order to address this problem, some systems may upload encrypted data to an untrusted server computer. Although data encryption is a well-known technique to protect sensitive personal information, encryption typically precludes searching. Thus, in order for a user to search an encrypted database for a desirable row, the user must first download and decrypt the entire database. This requires an excessive amount of bandwidth and processing, especially for large databases.
Embodiments of the invention address these and other problems.